home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / SNNSV32.ZIP / SNNSv3.2 / kernel / sources / cc_rcc_topo.c < prev    next >
C/C++ Source or Header  |  1994-04-25  |  15KB  |  489 lines
  1. /*****************************************************************************
  2.   FILE           : cc_rcc_topo.c
  3.   SHORTNAME      : 
  4.   SNNS VERSION   : 3.2
  5.  
  6.   PURPOSE        : Functions of CC and RCC for topological check.
  7.   NOTES          :
  8.  
  9.   AUTHOR         : Michael Schmalzl
  10.   DATE           : 5.2.93
  11.  
  12.   CHANGED BY     : Michael Schmalzl
  13.   IDENTIFICATION : @(#)cc_rcc_topo.c    1.8 3/15/94
  14.   SCCS VERSION   : 1.8
  15.   LAST CHANGE    : 3/15/94
  16.  
  17.              Copyright (c) 1990-1994  SNNS Group, IPVR, Univ. Stuttgart, FRG
  18.  
  19. ******************************************************************************/
  20.  
  21. #include <stdio.h>
  22. #include <math.h>
  23. #include <time.h>  
  24. #include <memory.h>
  25. #include <malloc.h>
  26. #include <values.h>
  27.  
  28. #include "kr_typ.h"    
  29. #include "kr_const.h"     
  30. #include "kr_def.h"     
  31. #include "kr_mac.h"
  32. #include "kernel.h"
  33. #include "cc_mac.h"    
  34. #include "cc_rcc.h" 
  35. #include "cc_rcc_topo.ph"
  36.  
  37.  
  38. /*****************************************************************************
  39.   FUNCTION : cc_clearFlags
  40.  
  41.   PURPOSE  : Clears all CC flags.
  42.   NOTES    :
  43.  
  44.   UPDATE   : 5.2.93
  45. ******************************************************************************/
  46.  
  47. static void cc_clearFlags(void)
  48. {
  49.  struct Unit *unitPtr;
  50.  
  51.  FOR_ALL_UNITS(unitPtr){
  52.    if(UNIT_IN_USE(unitPtr)){
  53.      unitPtr->flags &= ~UFLAG_REFRESH;
  54.      unitPtr->lln = 0;
  55.      LINKS_LEAVING(unitPtr) = 0;
  56.      LINKS_ARRIVEING(unitPtr) = 0;
  57.      INPUT_LINKS(unitPtr) = 0;
  58.    }
  59.  }
  60. } 
  61.  
  62. /*****************************************************************************
  63.   FUNCTION : rcc_clearFlags
  64.  
  65.   PURPOSE  : Clears all RCC flags.
  66.   NOTES    :
  67.  
  68.   UPDATE   : 5.2.93
  69. ******************************************************************************/
  70.  
  71. static void rcc_clearFlags(void)
  72. {
  73.  struct Unit *unitPtr;
  74.  int flagMask;
  75.  
  76.  flagMask = RCC_FLAG | UFLAG_REFRESH;
  77.  FOR_ALL_UNITS(unitPtr){
  78.    if(UNIT_IN_USE(unitPtr)){
  79.      unitPtr->flags &= ~flagMask;
  80.      unitPtr->lln = 0;
  81.      LINKS_LEAVING(unitPtr) = 0;
  82.      LINKS_ARRIVEING(unitPtr) = 0;
  83.      INPUT_LINKS(unitPtr) = 0;
  84.    }
  85.  }
  86. } 
  87.  
  88. /*****************************************************************************
  89.   FUNCTION : cc_quicksort
  90.  
  91.   PURPOSE  : Sorts  the units of the hidden layer by  the number of incomming
  92.              links.
  93.   NOTES    :
  94.  
  95.   UPDATE   : 5.2.93
  96. ******************************************************************************/
  97.  
  98. static void cc_quicksort(int left, int right)
  99. {
  100.  int i,last;
  101.  struct Unit *temp;
  102.  
  103.  if(left >= right ){
  104.    return;
  105.  }
  106.  temp = FirstHiddenUnitPtr[left]; 
  107.  FirstHiddenUnitPtr[left] = FirstHiddenUnitPtr[(left+right)/2]; 
  108.  FirstHiddenUnitPtr[(left+right)/2] = temp;  
  109.  last = left; 
  110.  for(i=left+1;i<=right;i++){
  111.    if(LINKS_LEAVING(FirstHiddenUnitPtr[i]) < LINKS_LEAVING(FirstHiddenUnitPtr[left])) {
  112.      temp = FirstHiddenUnitPtr[++last]; 
  113.      FirstHiddenUnitPtr[last]=FirstHiddenUnitPtr[i]; 
  114.      FirstHiddenUnitPtr[i]=temp;
  115.    }
  116.  }
  117.  temp = FirstHiddenUnitPtr[left]; 
  118.  FirstHiddenUnitPtr[left]=FirstHiddenUnitPtr[last]; 
  119.  FirstHiddenUnitPtr[last] = temp;
  120.  cc_quicksort(left,last);
  121.  cc_quicksort(last+1,right);
  122. }
  123.  
  124.  
  125. /*****************************************************************************
  126.   FUNCTION : DepthFirst4
  127.  
  128.   PURPOSE  : Depth search routine for topological sorting.
  129.   NOTES    :
  130.  
  131.   UPDATE   : 5.2.93
  132. ******************************************************************************/
  133.  
  134. static void  DepthFirst4(struct Unit *unit_ptr, int depth )
  135. {
  136.   struct Site   *site_ptr;
  137.   struct Link   *link_ptr;
  138.  
  139.  
  140.   if (unit_ptr->flags & UFLAG_REFRESH)
  141.     {  /*  the 'touch' flag is set: don't continue search  */
  142.     topo_msg.src_error_unit = unit_ptr - unit_array; /*  store unit number  */
  143.  
  144.     if IS_OUTPUT_UNIT( unit_ptr )
  145.       {  /*  this output unit has a output connection to another unit  */
  146.       if (topo_msg.error_code == KRERR_NO_ERROR)
  147.         topo_msg.error_code = KRERR_O_UNITS_CONNECT;
  148.     }
  149.     else
  150.       if (unit_ptr->lln == 0)
  151.         {  /*  logical layer no. isn't set => Cycle found  */
  152.         topo_msg.no_of_cycles++;
  153.         if (topo_msg.error_code == KRERR_NO_ERROR)
  154.           topo_msg.error_code = KRERR_CYCLES;
  155.       }
  156.  
  157.     return;
  158.   }
  159.   else
  160.     /*  set the 'touch' flag  */
  161.     unit_ptr->flags |= UFLAG_REFRESH;
  162.  
  163.   switch (unit_ptr->flags & UFLAG_INPUT_PAT)
  164.     {
  165.     case  UFLAG_DLINKS:   /*  unit has direct links  */
  166.       FOR_ALL_LINKS(unit_ptr,link_ptr){
  167.         DepthFirst4( link_ptr->to, depth + 1 );  /*  increase depth  */
  168.         if(IS_INPUT_UNIT(link_ptr->to)){
  169.           INPUT_LINKS(unit_ptr)++;
  170.         }
  171.         if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
  172.           LINKS_LEAVING(link_ptr->to)++;
  173.           LINKS_ARRIVEING(unit_ptr)++;
  174.         }
  175.       }
  176.       break;
  177.     case  UFLAG_SITES:  /*  unit has sites  */
  178.       FOR_ALL_SITES_AND_LINKS(unit_ptr,site_ptr, link_ptr) {
  179.         DepthFirst4( link_ptr->to, depth + 1 );  /*  increase depth  */
  180.         if(IS_INPUT_UNIT(link_ptr->to)){
  181.           INPUT_LINKS(unit_ptr)++;
  182.         }
  183.         if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
  184.           LINKS_LEAVING(link_ptr->to)++;
  185.           LINKS_ARRIVEING(unit_ptr)++;
  186.         }
  187.       }
  188.       break;
  189.   }
  190.  
  191.   /*  remember the depth (for cycle detection and statistics)  */
  192.   unit_ptr->lln = depth;
  193.  
  194.   /*  store only hidden units  */
  195.   if IS_HIDDEN_UNIT( unit_ptr )
  196.     *global_topo_ptr++ = unit_ptr;  /*  store sorted unit pointer  */
  197. }
  198.  
  199. /*****************************************************************************
  200.   FUNCTION : DepthFirst5
  201.  
  202.   PURPOSE  : Depth search routine for topological sorting.
  203.   NOTES    :
  204.  
  205.   UPDATE   : 5.2.93
  206. ******************************************************************************/
  207.  
  208. static void  DepthFirst5( unit_ptr, depth )
  209. struct Unit   *unit_ptr;
  210. int     depth;
  211. {
  212.   struct Site   *site_ptr;
  213.   struct Link   *link_ptr;
  214.  
  215.  
  216.   if (unit_ptr->flags & UFLAG_REFRESH)
  217.     {  /*  the 'touch' flag is set: don't continue search  */
  218.     topo_msg.src_error_unit = unit_ptr - unit_array; /*  store unit number  */
  219.  
  220.     if IS_OUTPUT_UNIT( unit_ptr )
  221.       {  /*  this output unit has a output connection to another unit  */
  222.       if (topo_msg.error_code == KRERR_NO_ERROR)
  223.         topo_msg.error_code = KRERR_O_UNITS_CONNECT;
  224.     }
  225.     else
  226.       if (unit_ptr->lln == 0)
  227.         {  /*  logical layer no. isn't set => Cycle found  */
  228.         topo_msg.no_of_cycles++;
  229.         if (topo_msg.error_code == KRERR_NO_ERROR)
  230.           topo_msg.error_code = KRERR_CYCLES;
  231.       }
  232.  
  233.     return;
  234.   }
  235.   else
  236.     /*  set the 'touch' flag  */
  237.     unit_ptr->flags |= UFLAG_REFRESH;
  238.  
  239.   switch (unit_ptr->flags & UFLAG_INPUT_PAT)
  240.     {
  241.     case  UFLAG_DLINKS:   /*  unit has direct links  */
  242.       FOR_ALL_LINKS(unit_ptr,link_ptr) {
  243.         if((IS_HIDDEN_UNIT(unit_ptr)) && (link_ptr->to == unit_ptr)) {
  244.           if(unit_ptr->flags & RCC_FLAG) {
  245.             topo_msg.error_code = KRERR_CC_ERROR4; /* too manny recurent links */
  246.           }
  247.           else { 
  248.             unit_ptr->flags |= RCC_FLAG;
  249.           }
  250.         }
  251.         else { 
  252.           DepthFirst5( link_ptr->to, depth + 1 );  /*  increase depth  */
  253.           if(IS_INPUT_UNIT(link_ptr->to)){
  254.             INPUT_LINKS(unit_ptr)++;
  255.           }
  256.           if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
  257.             LINKS_LEAVING(link_ptr->to)++;
  258.             LINKS_ARRIVEING(unit_ptr)++;
  259.           }
  260.         }
  261.       }
  262.       break;
  263.     case  UFLAG_SITES:  /*  unit has sites  */
  264.       FOR_ALL_SITES_AND_LINKS(unit_ptr,site_ptr, link_ptr) {
  265.         if((IS_HIDDEN_UNIT(unit_ptr)) && (link_ptr->to == unit_ptr)) {
  266.           if(unit_ptr->flags & RCC_FLAG) {
  267.             topo_msg.error_code = KRERR_CC_ERROR4; /* too many recurent links */
  268.           }
  269.           else { 
  270.             unit_ptr->flags |= RCC_FLAG;
  271.           }
  272.         }
  273.         else { 
  274.           DepthFirst5( link_ptr->to, depth + 1 );  /*  increase depth  */
  275.           if(IS_INPUT_UNIT(link_ptr->to)){
  276.             INPUT_LINKS(unit_ptr)++;
  277.           }
  278.           if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
  279.             LINKS_LEAVING(link_ptr->to)++;
  280.             LINKS_ARRIVEING(unit_ptr)++;
  281.           }
  282.         }
  283.       }
  284.       break;
  285.     }
  286.  
  287.   /*  remember the depth (for cycle detection and statistics)  */
  288.   unit_ptr->lln = depth;
  289.  
  290.   /*  store only hidden units  */
  291.   if IS_HIDDEN_UNIT( unit_ptr )
  292.     *global_topo_ptr++ = unit_ptr;  /*  store sorted unit pointer  */
  293. }
  294.  
  295. /*****************************************************************************
  296.   FUNCTION : cc_topoSort
  297.  
  298.   PURPOSE  : Main routine for topological sorting for CC and RCC.
  299.   NOTES    :
  300.  
  301.   UPDATE   : 5.2.93
  302. ******************************************************************************/
  303.  
  304. krui_err cc_topoSort(int topoSortId)
  305. {
  306.   register struct Unit   *unit_ptr;
  307.   int   io_units,h,counter=0,recurentLinkDetected;
  308.   struct Link *link_ptr;
  309.   
  310.   KernelErrorCode = KRERR_NO_ERROR;  /*  reset return code  */
  311.   if(topoSortId == TOPOLOGICAL_CC) {
  312.     cc_clearFlags();    /*  reset units 'touch' flags  */
  313.   }
  314.   else {
  315.     rcc_clearFlags();
  316.   }
  317.   global_topo_ptr = topo_ptr_array;  /*  initialize global pointer */
  318.  
  319.   /*  limit left side of the topological array with NULL pointer  */
  320.   *global_topo_ptr++ = NULL;
  321.  
  322.   /*  put all input units in the topologic array  */
  323.   io_units = 0;
  324.   FOR_ALL_UNITS( unit_ptr ) 
  325.     if (IS_INPUT_UNIT( unit_ptr ) && UNIT_IN_USE( unit_ptr ))
  326.       {
  327.       if UNIT_HAS_INPUTS( unit_ptr )
  328.         {  /*  this input unit has a connection to another unit  */
  329.         topo_msg.dest_error_unit = unit_ptr - unit_array;  /*  store the unit no.  */
  330.  
  331.         KernelErrorCode = KRERR_I_UNITS_CONNECT;  /*  input unit has input  */
  332.         return( KernelErrorCode );
  333.       }
  334.  
  335.       io_units++;       /*  there is a input unit  */
  336.       *global_topo_ptr++ = unit_ptr;  /*  save input unit  */
  337.     }
  338.   
  339.   if ((NoOfInputUnits = io_units) == 0)
  340.     {  /*  no input units */
  341.     KernelErrorCode = KRERR_NO_INPUT_UNITS;
  342.     return( KernelErrorCode );
  343.   }
  344.  
  345.   /*  limit input units in the topological array with NULL pointer  */
  346.   *global_topo_ptr++ = NULL;
  347.  
  348.   /*  begin depth search at the first output unit  */
  349.   io_units = 0;
  350.   FOR_ALL_UNITS( unit_ptr )
  351.     if (IS_OUTPUT_UNIT( unit_ptr ) && UNIT_IN_USE( unit_ptr ))
  352.       {
  353.       io_units++;       /*  there is a output unit  */
  354.       if(topoSortId == TOPOLOGICAL_CC){
  355.         DepthFirst4( unit_ptr, 1 );
  356.       }
  357.       else if (topoSortId == TOPOLOGICAL_RCC){
  358.         DepthFirst5(unit_ptr,1);
  359.       }
  360.       else { /* topoSortId == TOPOLOGICAL_BCC */ 
  361.         DepthFirst4(unit_ptr,1);
  362.       }      
  363.       if (topo_msg.error_code != KRERR_NO_ERROR)
  364.         {  /*  stop if an error occured  */
  365.         KernelErrorCode = topo_msg.error_code;
  366.         return( KernelErrorCode );
  367.       }
  368.     }
  369.  
  370.  
  371.   if ((NoOfOutputUnits = io_units) == 0)
  372.     {  /*  no output units */
  373.     KernelErrorCode = KRERR_NO_OUTPUT_UNITS;
  374.     return( KernelErrorCode );
  375.   }
  376.  
  377.   /*  limit hidden units in the topological array with NULL pointer  */
  378.   *global_topo_ptr++ = NULL;
  379.  
  380.   /*  put all output units in the topological array  */
  381.   FOR_ALL_UNITS( unit_ptr ) 
  382.     if (IS_OUTPUT_UNIT(unit_ptr ) && UNIT_IN_USE( unit_ptr ))
  383.       *global_topo_ptr++ = unit_ptr;  /*  save output unit  */
  384.  
  385.   /*  limit right side of the topologic array with NULL pointer  */
  386.   *global_topo_ptr++ = NULL;
  387.   
  388.   FOR_ALL_UNITS( unit_ptr ) {
  389.     if (IS_SPECIAL_UNIT(unit_ptr) && UNIT_IN_USE( unit_ptr )) {
  390.       if(topoSortId == TOPOLOGICAL_RCC){
  391.         link_ptr = (struct Link *) unit_ptr->sites;
  392.         if(unit_ptr != link_ptr->to) {
  393.           KernelErrorCode = KRERR_CC_ERROR9; /* the first link is not a recurent link */
  394.           return(KernelErrorCode);
  395.         }
  396.         recurentLinkDetected = 0;
  397.         if(topoSortId == TOPOLOGICAL_RCC) {   
  398.           FOR_ALL_LINKS(unit_ptr,link_ptr){
  399.             if(unit_ptr == link_ptr->to) {
  400.               recurentLinkDetected++;
  401.             }
  402.           }
  403.           if(recurentLinkDetected != 1) {   
  404.             KernelErrorCode = KRERR_CC_ERROR8; /* the special unit has too many links */
  405.             return( KernelErrorCode ); 
  406.       }
  407.     }
  408.       }
  409.       *global_topo_ptr++ = unit_ptr;  /*  save output unit  */
  410.       unit_ptr->flags |= UFLAG_REFRESH;
  411.     }
  412.   }
  413.   /*  limit right side of the topologic array with NULL pointer  */
  414.   *global_topo_ptr++ = NULL;
  415.  
  416.   /*  calc. no. of sorted units  */
  417.   no_of_topo_units = (global_topo_ptr - topo_ptr_array) - 5;
  418.  
  419.   /*  search for dead units i.e. units without inputs  */
  420.   FOR_ALL_UNITS( unit_ptr )
  421.     if (!(unit_ptr->flags & UFLAG_REFRESH) && UNIT_IN_USE( unit_ptr ))
  422.       {
  423.       topo_msg.no_of_dead_units++;
  424.       if (topo_msg.src_error_unit == 0)
  425.         topo_msg.src_error_unit = unit_ptr - unit_array;  /*  store the unit no.  */
  426.     }
  427.  
  428.   if (topo_msg.no_of_dead_units != 0)
  429.     KernelErrorCode = KRERR_DEAD_UNITS;
  430.  
  431.   if(KernelErrorCode == KRERR_NO_ERROR){
  432.     FirstHiddenUnitPtr = (struct Unit **)(&topo_ptr_array[1]) + NoOfInputUnits + 1;
  433.     FOR_ALL_HIDDEN_UNITS(unit_ptr,h){
  434.        switch(topoSortId){
  435.          case TOPOLOGICAL_RCC : 
  436.            if(!(unit_ptr->flags & RCC_FLAG)) {
  437.              KernelErrorCode = KRERR_CC_ERROR5;
  438.            }
  439.            if((LINKS_LEAVING(unit_ptr)+LINKS_ARRIVEING(unit_ptr)+1)!=NoOfHiddenUnits) {
  440.              KernelErrorCode = KRERR_CC_ERROR6;
  441.              return(KernelErrorCode);
  442.            }
  443.            if(LINKS_ARRIVEING(unit_ptr) != counter++) {
  444.              KernelErrorCode = KRERR_CC_ERROR6;
  445.              return(KernelErrorCode);
  446.            }
  447.            link_ptr = (struct Link *) unit_ptr->sites;
  448.            if(unit_ptr != link_ptr->to) {
  449.              KernelErrorCode = KRERR_CC_ERROR7; /* the first link is not the recurent link */
  450.              return(KernelErrorCode);
  451.            }
  452.          break;
  453.          case TOPOLOGICAL_CC : 
  454.            if((LINKS_LEAVING(unit_ptr)+LINKS_ARRIVEING(unit_ptr)+1)!=NoOfHiddenUnits) {
  455.              fprintf(stderr,"111111 %d \n",NoOfHiddenUnits);
  456.              KernelErrorCode = KRERR_CC_ERROR6;
  457.              return(KernelErrorCode);
  458.            }
  459.            if(LINKS_ARRIVEING(unit_ptr) != counter++) {
  460.              fprintf(stderr,"22222 %d \n",counter);
  461.              KernelErrorCode = KRERR_CC_ERROR6;
  462.              return(KernelErrorCode);
  463.            }
  464.          break;
  465.          case TOPOLOGICAL_BCC : 
  466.            if((LINKS_LEAVING(unit_ptr)+LINKS_ARRIVEING(unit_ptr)+1)!=NoOfHiddenUnits) {
  467.              KernelErrorCode = KRERR_CC_ERROR6;
  468.              return(KernelErrorCode);
  469.            }
  470.            if(LINKS_ARRIVEING(unit_ptr) != counter++) {
  471.              KernelErrorCode = KRERR_CC_ERROR6;
  472.              return(KernelErrorCode);
  473.            }
  474.            if(counter == NoOfHiddenUnits) {
  475.              counter = 0;
  476.            }
  477.          break;
  478.        }  
  479.     }
  480.   }
  481.   return( KernelErrorCode );
  482. }
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.